#include "heap.h"

void Swap(int* a,int *b) {
	HPdatatype x = *a;
	*a = *b;
	*b = x;
}

void upadjust(HPdatatype* a,int son) {
	int p = (son - 1) / 2;
	while (son) {
		if (a[p] < a[son]) {
			Swap(&a[p], &a[son]);
			son = p;
			p= (son - 1) / 2;
		}
		else
			break;
	}
}
void downadjust(HPdatatype* a,int n,int p) {
	int son = p * 2 + 1;
	while (son < n) {
		if (son + 1 < n && a[son + 1] > a[son])
			son++;
		if (a[son] > a[p]) {
			Swap(&a[son], &a[p]);
			p = son;
			son = p * 2 + 1;
		}
		else
			break;
	}
}

void HPInit(HP* php) {
	assert(php);
	php->a = (int*)malloc(sizeof(int) * 4);
	if (php->a == NULL) {
		perror("malloc faild");
	}
	php->capacity = 4;
	php->size = 0;
}
void HPpush(HP* php, HPdatatype x) {
	if (php->size == php->capacity) {
		int* tmp = (int*)realloc(php->a,sizeof(int) * php->capacity * 2);
		if (!tmp) {
			perror("malloc faild");
		}
		php->a = tmp;
		php->capacity *= 2;
	}
	
	php->a[php->size] = x;
	upadjust(php->a, php->size);
	php->size++;
}
void HPpop(HP* php) {
	assert(php);
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	downadjust(php->a,php->size,0);
	
}
HPdatatype HPtop(HP* php) {
	assert(php);
	return php->a[0];
}
bool HPempty(HP* php) {
	assert(php);
	return php->size == 0;
}
int HPsize(HP* php) {
	assert(php);
	return php->size;
}